package databook;

import databook.filter.DataFilter;
import databook.filter.FilterEvent;
import databook.util.CountingHash;
import databook.util.MajorMap;
import databook.controller.*;

import java.util.Iterator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Vector;
import java.util.Set;
import java.util.Collection;
import java.util.Collections;
import java.util.Enumeration;
import java.util.Arrays;

import javax.swing.tree.TreeNode;
//import javax.swing.JCheckBox;

import java.awt.Color;
import java.awt.event.ItemEvent;
import java.awt.event.ItemListener;

import prefuse.data.Table;
import prefuse.data.Tuple;
//import prefuse.util.collections.IntIterator;

/**
 * A Weighted Tree data structure.  Each node keeps track of its kids
 * weight and is able to report on it to its parent.
 * 
 * The tree is populated by entering in String arrays that correspond
 * to a list of headers that the tree is built on. For example,
 * with a list of headers of ['MAJOR','TERM','GENDER','RACE'] you would
 * pass an array like ['CMSC','2007-01','M','Asian','20'] to the add() function.
 * The last entry is the weight to give to that leaf of the tree.  So the length
 * of the added array should be one more than the header length.  This can be changed
 * to keep a "WEIGHT" header value, or to simply accumulate as like nodes are entered
 * into the tree.  But this will speed up entry, as we can store the precomputed
 * weights in a file and simple read them into this data structure.
 * 
 * Once populated the data structure can store node references into the edge and node
 * tables of the Major Graph.  So for the node graph, each node will find its corresponding
 * tree.  That is, any entered data that starts with ['major',...].  Similarly, each
 * node will have its node associated with the header and values of 
 * ['NODE_FROM','NODE_TO',"TERM','GENDER'...] -> ['CMSC','IFMS'...].  Since Java
 * uses references for objects, the data structure is only stored and populated
 * once.  So we can store as many references as it takes and it wouldn't be any more
 * space than saving the integer (minus the original tree).  
 * 
 * In order the graph to figure out the weight value for an edge or node it will
 * grab the tree from the table (under "TREE_W" or "TREE" or something), and return
 * tree.getWeight().  
 * 
 * So what is the advantage?  WeightTree will automatically figure out which branches
 * to calculate weight on based on the filter panel.  This is done using the event
 * model commonly used by Java.  Every time a value changes in the control panel, an
 * event will be sent to the DatabookViz object, which will tell the graph to recalculate
 * its values for weight and color.  When they ask WeightTree again, WeightTree will 
 * know which values the control panel are showing.  So for each node, it will check
 * that its value is shown.  If it is not, then it will not traverse the tree anymore
 * and will return 0.  So if only one year is being shown, then none of the branches
 * associated with years not shown will even be queried.  So we want to find out
 * which parameters they are most likely to query on, and stick them higher up
 * the hierarchy.  
 * 
 * For efficiency WeightTree caches its weights, so when color queries for the weight
 * right after the size action item, then only one node will be queried since that
 * cache is set.  If a filter value changes, then caches are reset and the full tree
 * is queried.  Working on making it a smarter caching reset, so only values pertaining
 * to the values changed in the filter will reset.
 *   
 * @author zach
 */
public class WeightTree implements TreeNode, PropertyListener, ItemListener, Comparable {

    private String[] hierarchy = null;
    private HashMap<String,String> filterMap;
    private int level = 0;
    private String value;
    private HashMap<String,WeightTree> children;
    private boolean leaf;
    private boolean show;
    private int weight = 0;
    private String filterHeader;
    private int fullWeight = 0;
    private Vector vector;
    
    private WeightTree parent;
    private WeightTree source;
    private WeightTree target;
    //private DataFilter filter;
    private FilterCheckBox checkbox;
    
    // Caches
    private boolean weight_cache = false;
    private boolean full_weight_cache = false;
    private boolean filter_cache = false;
    private boolean show_cache = false;
    
    private boolean use_cache = true;
        
    // Accounting Values
    private int weight_count = 0;
    private int full_weight_count = 0;
    private int max_count = 0;
    private int min_count = 0;
    private int hier_count = 0;
    private int filter_count = 0;
    
    public WeightTree(String[] h) {
        this.hierarchy = h;
        init();
    }
    
    public WeightTree(Table table) {
        this(table,null);
    }
    
    public WeightTree(Table table, HashMap map) {
        hierarchy = new String[table.getColumnCount()-1];
        for (int i = 0; i < hierarchy.length; i++) {
            hierarchy[i] = table.getColumnName(i);
        }
        filterMap = map;
        init();
        for (int i = 0; i < table.getTupleCount(); i++) {
            Tuple row = table.getTuple(i);
            String[] values = new String[row.getColumnCount()-1];
            for (int j = 0; j < values.length; j++) {
                values[j] = row.getString(j);
            }
            add(values,Integer.parseInt(row.getString(row.getColumnCount()-1)));
        }
    }
    
    public WeightTree(WeightTree p, int i, String value) {
        this.parent = p;
        this.level = i;
        this.value = value;
        init();
    }
    
    public void init() {
        children = new HashMap();
        //System.out.println("Add for WT: " + getFilterValue() + " " + value);
        if (!isRoot()) Props.addFilterListener(getFilterValue(),value,this);
    }
    
    public void add(String[] arr) {
        add(arr,1);
    }
    
    public boolean add(String[] arr, int w) {
        vector = null;
        if (isRoot() && arr.length != getHierarchy().length) 
            return false;
        
        if (level == arr.length) {
            weight += w;
            leaf = true;
            return true;
        } else {
            if (!children.containsKey(arr[level])) {
                children.put(arr[level],new WeightTree(this,level+1,arr[level]));
            }
            return children.get(arr[level]).add(arr,w);
        }
    }
    
    
    public void setNodes(WeightTree s, WeightTree t) {
        source = s;
        target = t;
    }
    
    public void propertyChanged(PropertyEvent evt) {
        if (!use_cache) return;
        if (((Boolean)evt.value).booleanValue() != show) {
            resetParentWeightCache();
            resetChildShowCache();
        }
        //System.out.println("Both show and weight should be set to false:  " + show_cache + " " + weight_cache);
    }
    
    public void resetChildShowCache() {
        show_cache = false;
        weight_cache = false;
        Iterator iter = children.values().iterator();
        while(iter.hasNext()) {
            ((WeightTree)iter.next()).resetChildShowCache();
        }
    }
    
    public void resetParentWeightCache() {
        weight_cache = false;
        show_cache = false;
        if(!isRoot()) {
            parent.resetParentWeightCache();
        }
    }
    
    public WeightTree getChild(String child) {
        if (children.containsKey(child))
            return children.get(child);
        else 
            return null;
    }
    
    public boolean isRoot() {
        return parent == null;
    }
    
    public String[] getHierarchy() {
        hier_count++;
        if (isRoot()) return hierarchy;
        else return parent.getHierarchy();
    }
    
    public String getFilterValue() {
        if (use_cache && filter_cache && filterHeader != null)
            return filterHeader;
        filterHeader = getFilterValue(level-1);
        filter_cache = true;
        return filterHeader;
    }
    
    public String getFilterValue(int l) {
        filter_count++;
        if (!isRoot()) {
            return parent.getFilterValue(l);
        } else {
            if (filterMap != null && l >= 0 && filterMap.containsKey(hierarchy[l])) {
                return filterMap.get(hierarchy[l]);
            } else if (l < 0) {
                return null;
            } else {
                return hierarchy[l];
            }
        }
    }
    
    public boolean filterNode() {
        if (use_cache && show_cache) 
            return show;
        if (isRoot()) {
            show = true;
            show_cache = true;
        } else { 
            show = Props.filter(getFilterValue(),value) && parent.filterNode();
            show_cache = true;
        }
        return show;
    }
    
    public WeightTree getRoot() {
        if (isRoot()) return this;
        else return parent.getRoot();
    }
    
    public double getSize() {
        return getSize(false);
    }
    
    public double getSize(boolean full) {
        if (Props.getBoolean(Props.PERCENT_IN)) {
            return getPercentage(target,full);
        } else if (Props.getBoolean(Props.PERCENT_OUT)) {
            return getPercentage(source,full);
        } else {
            return (full ? getFullWeight() : getWeight());
        }
    }
    
    public double getPercentage(WeightTree node,boolean full) {
        try {
            if (node == null) {
                double nodew = getRoot().getWeight();
                if (nodew == 0) return 0;
                return getWeight()/nodew;
            } else {
                double nodew = node.getWeight();
                if (nodew == 0) return 0;
                //System.out.println("Edge Percentage: " + value + " of " + node.value + " => " + getWeight() + " " + node.getWeight() + " " + getWeight()/(double)node.getWeight());
                //if (getWeight() > node.getWeight()) {
                    //System.out.println(printTree(false));
                    //System.out.println(node.printTree(false));
                //}
                //System.out.println("Edge Weight: " + this.getWeight() + " " + node.getWeight() + " " + (getWeight()/(double)node.getWeight()));
                return this.getWeight()/nodew;
            }
        } catch (ArithmeticException ae) {
            System.out.println("This is no good");
            return 0;
        }
    }
    
    public int getWeight() {
        if (use_cache && weight_cache && (show_cache || filterNode())) {
            return weight;
        }
        if (isRoot() || filterNode()) {  
            if (!leaf) {
                Iterator<WeightTree> iter = children.values().iterator();
                int sum = 0;
                while(iter.hasNext()) {
                    sum += iter.next().getWeight();
                }
                weight = sum;
            }
        } else {
            if (!leaf)
                weight = 0;
            else 
                return 0;       // Don't want to set a leaf's weight to zero because it's permanent.
                                // So don't bother cacheing the leaf.  Wont save much anyway
        }
        weight_cache = true;
        return weight;
    }

    public int getFullWeight() {
        if (leaf)
            return weight;
        
        if (use_cache && full_weight_cache) {
            return fullWeight;
        }
        
        Iterator<WeightTree> iter = children.values().iterator();
        int sum = 0;
        while(iter.hasNext()) {
            sum += iter.next().getFullWeight();
        }
        fullWeight = sum;
        full_weight_cache = true;
        return fullWeight;
    }
    
    public double getMaxSize(String field, boolean full) {
        return getMaxSize(field,full, null);
    }
    public double getMaxSize(String field, boolean full, String unique) {
        return getMaxSize(field,full,unique,false);
    }
    
    public double getMaxSize(String field, boolean full, String unique, boolean edge) {
        if ((Props.getBoolean(Props.PERCENT_IN) || Props.getBoolean(Props.PERCENT_OUT))) {
            if (full) return 1;
            return getMaxPercentage(field,full,unique,edge);
        } else {
            return getMaxWeight(field,full,unique);
        }
    }
    
    public double getMaxPercentage(String field,boolean full,String unique, boolean edge) {
        if (edge) {
            if (source != null) {
                return getSize();
            }
            double max = 0;
            Iterator iter = children.values().iterator();
            while (iter.hasNext()) {
                double tmp = ((WeightTree)iter.next()).getMaxPercentage(field,full,unique,edge);
                if (tmp > max) max = tmp;
            }
            return max;
        } else {
            try {
                return getMaxWeight(field,full,unique)/(double)(full ? getRoot().getFullWeight() : getRoot().getWeight());
            }catch (Exception e) {
                System.out.println("Exception! " + e);
                return 0;
            }
        }
    }
    
    public int getMaxWeight(String field) {
        return getCounts(false).getMax(field,false);
    }
    
    public int getMaxWeight(String field, boolean full) {
        return getCounts(full).getMax(field,full);
    }
    
    public int getMaxWeight(String field,boolean full,String unique) {
        if (unique == null || (getHierValue().equals(unique) && !value.equals(parent.value))) {
            return getCounts(full).getMax(field,full);
        } else {
            Iterator iter = children.values().iterator();
            int max = 0;
            while (iter.hasNext()) {
                int tmp = ((WeightTree)iter.next()).getMaxWeight(field,full,unique);
                if (tmp > max) max = tmp;
            }
            return max;
        }
    }
        
    public String getHierValue() {
        if (isRoot()) return "";
        else return getHierarchy()[level-1];
    }   
    
    /*
    public double getMinSize() {
        return getMinSize(0);
    }
    
    public double getMin(boolean full) {
        return getMinSize(0,full);
    }
    
    public double getMinSize(String l, boolean full) {
        return getMinSize(getIndex(l),full);
    }
    
    public double getMinSize(int level) {
        return getMinSize(level,false);
    }/**/
    public double getMinSize(String field, boolean full) {
        return getMinSize(field,full, null);
    }
    
    public double getMinSize(String field, boolean full, String unique) {
        return getMinSize(field,full,unique,false);
    }
    
    public double getMinSize(String field, boolean full, String unique, boolean edge) {
        if ((Props.getBoolean(Props.PERCENT_IN) || Props.getBoolean(Props.PERCENT_OUT))) {
            if (full) return 0;
            return getMinPercentage(field,full,unique,edge);
        } else {
            return getMinWeight(field,full,unique);
        }
    }
    
    public double getMinPercentage(String field,boolean full,String unique, boolean edge) {
        if (edge) {
            if (source != null) {
                return getSize();
            }
            double min = -1;
            Iterator iter = children.values().iterator();
            while (iter.hasNext()) {
                double tmp = ((WeightTree)iter.next()).getMaxPercentage(field,full,unique,edge);
                if (tmp < min || min == -1) min = tmp;
            }
            return min;
        } else {
            try {
                return getMinWeight(field,full,unique)/(double)(full ? getRoot().getFullWeight() : getRoot().getWeight());
            }catch (Exception e) {
                System.out.println("Exception! " + e);
                return 0;
            }
        }
    }
    
    public double getMinWeight(String field) {
        return getCounts(false).getMin(field,false);
    }
    
    public double getMinWeight(String field, boolean full) {
        return getCounts(full).getMin(field,full);
    }
    
    public double getMinWeight(String field,boolean full,String unique) {
        if (unique == null || (getHierValue().equals(unique) && !value.equals(parent.value))) {
            return getCounts(full).getMin(field,full);
        } else {
            Iterator iter = children.values().iterator();
            double min = -1;
            while (iter.hasNext()) {
                double tmp = ((WeightTree)iter.next()).getMinWeight(field,full,unique);
                if (tmp < min || min == -1) min = tmp;
            }
            return min;
        }
    }
    
    /*public double getMinSize(int level,boolean full) {
        if (full && Props.usePercent()) return 0;
        min_count++;
        double min = -1;
        Iterator<WeightTree> iter = children.values().iterator();
        while(iter.hasNext()) {
            double tmp;
            if (level > 0) 
                tmp = iter.next().getMin(level-1,full);
            else if (full)
                tmp = iter.next().getFullWeight();
            else
                tmp = iter.next().getSize();
            if (min > tmp || min == -1)
                min = tmp;
        }
        //System.out.println("Returning: " + min);
        return min;
    }/**/
    
    /*public boolean resetWeightCache(FilterEvent fe) {
        //if (fe.value.equals(value)) System.out.println("Value: " + value + " Event: " + fe);
        if (!use_cache) return false;
        show_cache = false;
        boolean change = false;
        String f = getFilterValue();
        if (f != null && f.equals(fe.property)) {
            change = true;
        }
        Iterator<WeightTree> iter = children.values().iterator();
        while(iter.hasNext()) {
            if (iter.next().resetWeightCache(fe))
                change = true;
        }
        if (change)
            weight_cache = false;
        return !weight_cache;
    }
    
    public void resetSingleWeightCache() {
        weight_cache = false;
    }
    
    public void resetFilterCache() {
        if (!use_cache) return;
        filter_cache = false;
        Iterator<WeightTree> iter = children.values().iterator();
        while(iter.hasNext()) {
            iter.next().resetFilterCache();
        }
    }/**/
    
    public Vector getValueArr() {
        if (leaf) {
            Vector<String> v = new Vector();
            WeightTree node = this;
            do {
                v.add(node.getValue());
                node = node.parent;
            } while (v != null);
            return v;
        }
        return new Vector();
    }
    
    public Collection getNodes(String prop) {
        return getNodes(getIndex(prop));
    }
    
    public Collection getNodes(int i) {
        if (i == -1) return new java.util.HashSet();
        if (level == i) {
            return children.values();
        }
        Vector v = new Vector();
        Iterator<WeightTree> iter = children.values().iterator();
        while(iter.hasNext()) {
            v.addAll(iter.next().getNodes(i));
        }
        return v;
    }/**/
    
    public Set getValues(String prop) {
        return getValues(getIndex(prop));
    }
    
    public Set getValues(int i) {
        if (i == -1) return new java.util.HashSet();
        if (level == i) {
            return children.keySet();
        }
        HashSet set = new HashSet();
        Iterator<WeightTree> iter = children.values().iterator();
        while(iter.hasNext()) {
            set.addAll(iter.next().getValues(i));
        }
        return set;
    }
    
    public int getIndex(String prop) {
        if (isRoot()) {
            for (int i = 0; i < hierarchy.length; i++) {
                if (hierarchy[i].equals(prop))
                    return i;
            }
            return -1;
        } else {
            return parent.getIndex(prop);
        }
    }
    
    public String getValue() {
        return value;
    }
    
    public Collection getLinks(String start,String stop) {
        return getLinks(getIndex(start)+1,getIndex(stop)+1);
    }
    
    public Collection getLinks(int start, int stop) {
        Vector v = new Vector();
        if (start == (stop - 1)) {
            if (level == stop) {
                    v.add(new WeightTree[] {this.parent,this});
            } else {
                Iterator<WeightTree> iter = children.values().iterator();
                while(iter.hasNext()) {
                    v.addAll(iter.next().getLinks(start,stop));
                }
            }
        }
        return v;
    }

    public CountingHash getCounts() {
        return getCounts(false);
    }
    
    public CountingHash getCounts(boolean all) {
        CountingHash childCounts;
        if (isRoot())
            childCounts = new CountingHash();
        else
            childCounts = new CountingHash(getHierarchy()[level-1],value,(all ? getFullWeight() :getWeight()));
        Iterator<WeightTree> iter = children.values().iterator();
        while(iter.hasNext()) {
            WeightTree child = iter.next();
            if (all || child.filterNode()) childCounts.putAll(child.getCounts(all));
        }
        return childCounts;
    }
    
    public Table getStackedTable(String xfield, String yfield) {
        Table t = new Table();
        t.addColumn("VALUE",String.class);
        t.addColumn("PROP",String.class,xfield);
        
        Set yvalues = getValues(yfield);
        Iterator iter = yvalues.iterator();
        while (iter.hasNext()) {
            String key = (String)iter.next();
            //System.out.println(xfield + " StackedTable: " + key);
            t.addColumn(key,double.class);
        }
        //Set xvalues = getValues(xfield);
        String[] xvalues = (String[])getValues(xfield).toArray(new String[0]);
        Arrays.sort(xvalues);
        //System.out.println("StackedTable: " + xvalues + " " + xfield);
        
        setTuple(t,xfield,yfield,xvalues);
        return t;
    }
    
    public void setTuple(Table t, String x_axis, String y_axis,String[] x_headers) {
        String[] h = getHierarchy();
        if (h[level].equals(y_axis)) {
            Vector values = parent.getValueArr();
            for (int i = 0; i < x_headers.length; i++) {
                
                int row = -1;
                for (int j = 0; row == -1 && j < t.getRowCount(); j++) {
                    if (t.getString(j,"VALUE").equals(x_headers[i]))
                        row = j;
                }
                if (row == -1) {
                    row = t.addRow();
                    //Set X-Axis
                    t.set(row,"VALUE",x_headers[i]);
                }
                
                //Set weights
                Iterator iter = children.values().iterator();
                while(iter.hasNext()) {
                    WeightTree child = (WeightTree)iter.next();
                    CountingHash c = child.getCounts(true);
                    if (c.containsKey(x_axis,x_headers[i])) {
                        double prev = t.getDouble(row,child.getValue());
                        t.set(row,child.getValue(),prev + (double)c.getInt(x_axis,x_headers[i]));
                    }
                }
            }
        } else {
            Iterator iter = children.values().iterator();
            while(iter.hasNext()) {
                ((WeightTree)iter.next()).setTuple(t,x_axis,y_axis,x_headers);
            }
        }
    }
    
    /**
     * TreeNode Functions
     */
    
    public Enumeration children() {
        if (vector == null) populateVector();
        return vector.elements();
        
    }
    
    public TreeNode getChildAt(int ind) {
        if (vector == null) populateVector();
        return (TreeNode)vector.get(ind);
    }
    
    public int getIndex(TreeNode node) {
        if (vector == null) populateVector();
        return vector.indexOf(node);
    }
    
    public boolean getAllowsChildren() {
        return !isLeaf();
    }
    
    public TreeNode getParent() {
        return (TreeNode)parent;
    }
    
    public boolean isLeaf() {
        return !isRoot() && getFilterValue().equals("MAJOR");
    }
    
    public int getChildCount() {
        return children.size();
    }
    
    public void populateVector() {
        vector = new Vector(children.values());
        Collections.sort(vector);
    }
    
    public int compareTo(Object o) {
        return value.compareTo(((WeightTree)o).value);
    }        
    
    public FilterCheckBox getCheckBox() {
        if (checkbox == null) createCheckbox();
        return checkbox;
    }
    
    public void itemStateChanged(ItemEvent e) {
        //getFilter().setFilterValue(getFilterValue(),value,checkbox.isSelected());
        System.out.println("Sate Changed");
        Iterator kids = children.values().iterator();
        while(kids.hasNext()) {
            ((WeightTree)kids.next()).setEnable(checkbox.isSelected());
        }
    }
    
    public void setEnable(boolean enable) {
        if (checkbox != null) {
            checkbox.setEnabled(enable);
            Iterator kids = children.values().iterator();
            while(kids.hasNext()) {
                ((WeightTree)kids.next()).setEnable(enable);
            }
        }
            
    }
    
    public void createCheckbox() {
        if (checkbox == null) {
            checkbox = new FilterCheckBox(getCheckBoxValue(),getFilterValue(),value);
            checkbox.setBackground(Color.WHITE);
            if (!isRoot())
                checkbox.setEnabled(parent.filterNode());
            checkbox.addItemListener(this);
            Iterator iter = children.values().iterator();
            if (!isLeaf()) {
                while(iter.hasNext()) {
                    ((WeightTree)iter.next()).createCheckbox();
                }
            }
        }
    }
    
/*    public DataFilter getFilter() {
        if (isRoot()) return filter;
        if (filter == null) return parent.getFilter();
        return filter;
    }/**/
    
    public String getCheckBoxValue() {
        if (!isRoot() && getFilterValue().equals("MAJOR")) {
            return value + " (" + MajorMap.getMajorName(value) + ")";
        } else if (!isRoot() && getFilterValue().equals("COLLEGE")) {
            return value + " (" + MajorMap.getCollegeName(value) + ")";
        } else {
            return value;
        }
    }
    
    public void select() {
        if (checkbox == null) createCheckbox();
        if (checkbox.isEnabled()) 
            checkbox.setSelected(!checkbox.isSelected());
    }
    
    /**
     * Utility
     */
    
    public String printTree() {
        return printTree(-1,true);
    }
    
    public String printTree(boolean full) {
        return printTree(-1,full);
    }
    
    public String printTree(int depth,boolean full) {
        String str = "";
        for (int i = 0; i < level; i++) {
            str += "\t";
        }
        str += value + "\t" + this.getWeight() + " out of " + getFullWeight() + "\t" + filterNode() + "\n";
        if (depth != 0 && (full || filterNode())) {
            if (vector == null) populateVector();
            for (int i = 0; i < vector.size(); i++) {
                str += ((WeightTree)vector.get(i)).printTree(depth-1,full);
            }
        }
        return str;
    }
}
